home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 15 / CU Amiga Magazine's Super CD-ROM 15 (1997)(EMAP Images)(GB)[!][issue 1997-10].iso / CUCD / Graphics / Ghostscript / source / gxhint3.c < prev    next >
C/C++ Source or Header  |  1997-06-20  |  16KB  |  507 lines
  1. /* Copyright (C) 1994, 1995, 1996, 1997 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of Aladdin Ghostscript.
  4.   
  5.   Aladdin Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author
  6.   or distributor accepts any responsibility for the consequences of using it,
  7.   or for whether it serves any particular purpose or works at all, unless he
  8.   or she says so in writing.  Refer to the Aladdin Ghostscript Free Public
  9.   License (the "License") for full details.
  10.   
  11.   Every copy of Aladdin Ghostscript must include a copy of the License,
  12.   normally in a plain ASCII text file named PUBLIC.  The License grants you
  13.   the right to copy, modify and redistribute Aladdin Ghostscript, but only
  14.   under certain conditions described in the License.  Among other things, the
  15.   License requires that the copyright notice and this notice be preserved on
  16.   all copies.
  17. */
  18.  
  19. /* gxhint3.c */
  20. /* Apply hints for Type 1 fonts. */
  21. #include "math_.h"        /* for floor in fixed_mult_quo */
  22. #include "gx.h"
  23. #include "gserrors.h"
  24. #include "gxarith.h"
  25. #include "gxfixed.h"
  26. #include "gxmatrix.h"
  27. #include "gxchar.h"
  28. #include "gxfont.h"
  29. #include "gxfont1.h"
  30. #include "gxtype1.h"
  31. #include "gzpath.h"
  32.  
  33. /* ------ Path hints ------ */
  34.  
  35. /* Forward references */
  36. private void
  37.   apply_hstem_hints(P3(gs_type1_state *, int, gs_fixed_point *)),
  38.   apply_vstem_hints(P3(gs_type1_state *, int, gs_fixed_point *));
  39.  
  40.  
  41. /*
  42.  * Apply hints along a newly added tail of a subpath.
  43.  * Path segments require hints as follows:
  44.  *    Nearly vertical line: vstem hints at both ends.
  45.  *    Nearly horizontal line: hstem hints at both ends.
  46.  *    Curve with nearly vertical/horizontal start/end:
  47.  *      vstem/hstem hints at start/end.
  48.  * We also must take care to handle the implicit closing line for
  49.  * subpaths that aren't explicitly closed.
  50.  *
  51.  * Note that "upper" and "lower" refer to device coordinates, which are
  52.  * what we use throughout the Type 1 code; however, "horizontal" and
  53.  * "vertical" refer to the character space coordinate system.
  54.  */
  55. #define hint_vert_lower 1
  56. #define hint_vert_upper 2    /* must be > lower */
  57. #define hint_vert (hint_vert_lower | hint_vert_upper)
  58. #define hint_horz_lower 4
  59. #define hint_horz_upper 8    /* must be > lower */
  60. #define hint_horz (hint_horz_lower | hint_horz_upper)
  61. #define nearly_axial(dmajor, dminor)\
  62.   ((dminor) <= (dmajor) >> 4)
  63.  
  64. /* Determine which types of hints, if any, are applicable to a given */
  65. /* line segment. */
  66. private int near
  67. line_hints(const gs_type1_state *pcis, const gs_fixed_point *p0,
  68.   const gs_fixed_point *p1)
  69. {    fixed dx = p1->x - p0->x;
  70.     fixed dy = p1->y - p0->y;
  71.     fixed adx, ady;
  72.     bool xi = pcis->fh.x_inverted, yi = pcis->fh.y_inverted;
  73.     int hints;
  74.  
  75.     /*
  76.      * To figure out which side of the stem we are on, we assume that
  77.      * the inside of the filled area is always to the left of the edge,
  78.      * i.e., edges moving in -X or +Y in character space are on the
  79.      * "upper" side of the stem, while edges moving by +X or -Y are on
  80.      * the "lower" side.  (See section 3.5 of the Adobe Type 1 Font
  81.      * Format book.)
  82.      */
  83.  
  84.     /*
  85.      * Map the deltas back into character space.  This is essentially
  86.      * an inverse-distance-transform with the combined matrix,
  87.      * but we don't bother to undo the scaling, since it only matters
  88.      * for the axiality test and we don't care about situations where
  89.      * X and Y scaling are radically different.
  90.      */
  91.     if ( xi )
  92.       dx = -dx;
  93.     if ( yi )
  94.       dy = -dy;
  95.     if ( pcis->fh.axes_swapped )
  96.       { fixed t = dx; int ti = xi; dx = dy, xi = yi; dy = t, yi = ti;
  97.       }
  98.     adx = any_abs(dx);
  99.     ady = any_abs(dy);
  100.     /*
  101.      * Note that since upper/lower refer to device space, we must
  102.      * interchange them if the corresponding axis is inverted.
  103.      */
  104.     if ( dy != 0 && nearly_axial(ady, adx) )
  105.       { hints = (dy > 0 ? hint_vert_upper : hint_vert_lower);
  106.         if ( xi )
  107.           hints ^= (hint_vert_lower | hint_vert_upper);
  108.       }
  109.     else if ( dx != 0 && nearly_axial(adx, ady) )
  110.       { hints = (dx < 0 ? hint_horz_upper : hint_horz_lower);
  111.         if ( yi )
  112.           hints ^= (hint_horz_lower | hint_horz_upper);
  113.       }
  114.     else
  115.       hints = 0;
  116.     if_debug7('y', "[y]hint from 0x%lx(%g,%g) to 0x%lx(%g,%g) = %d\n",
  117.           (ulong)p0, fixed2float(p0->x), fixed2float(p0->y),
  118.           (ulong)p1, fixed2float(p1->x), fixed2float(p1->y),
  119.           hints);
  120.     return hints;
  121. }
  122.  
  123. /* Apply hints at a point.  Optionally return the amount of adjustment. */
  124. private void near
  125. apply_hints_at(gs_type1_state *pcis, int hints, gs_fixed_point *ppt,
  126.   gs_fixed_point *pdiff)
  127. {    fixed px = ppt->x, py = ppt->y;
  128.  
  129.     if_debug4('y', "[y]applying hints %d to 0x%lx(%g,%g) ...\n",
  130.           hints, (ulong)ppt, fixed2float(px), fixed2float(py));
  131.     if ( (hints & hint_vert) != 0 &&
  132.          (pcis->vstem_hints.count & pcis->dotsection_flag) != 0
  133.        )
  134.       apply_vstem_hints(pcis, (hints & hint_vert_upper) -
  135.                 (hints & hint_vert_lower), ppt);
  136.     if ( (hints & hint_horz) != 0 &&
  137.          (pcis->hstem_hints.count & pcis->dotsection_flag) != 0
  138.        )
  139.       apply_hstem_hints(pcis, (hints & hint_horz_upper) -
  140.                 (hints & hint_horz_lower), ppt);
  141.     if ( pdiff != NULL )
  142.       pdiff->x = ppt->x - px,
  143.       pdiff->y = ppt->y - py;
  144.     /* Here is where we would round *ppt to the nearest quarter-pixel */
  145.     /* if we wanted to. */
  146.     if_debug2('y', "[y] ... => (%g,%g)\n",
  147.           fixed2float(ppt->x), fixed2float(ppt->y));
  148. }
  149.  
  150. #ifdef DEBUG
  151. private void near
  152. add_hint_diff_proc(gs_fixed_point *ppt, fixed dx, fixed dy)
  153. {    if_debug7('y', "[y]adding diff (%g,%g) to 0x%lx(%g,%g) => (%g,%g)\n",
  154.           fixed2float(dx), fixed2float(dy), (ulong)ppt,
  155.           fixed2float(ppt->x), fixed2float(ppt->y),
  156.           fixed2float(ppt->x + dx),
  157.           fixed2float(ppt->y + dy));
  158.     ppt->x += dx;
  159.     ppt->y += dy;
  160. }
  161. #define add_hint_dxdy(pt, dx,dy)\
  162.   add_hint_diff_proc(&(pt), dx, dy)
  163. #else
  164. #define add_hint_dxdy(pt, dx, dy)\
  165.   (pt).x += (dx), (pt).y += (dy)
  166. #endif
  167. #define add_hint_diff(pt, diff)\
  168.   add_hint_dxdy(pt, (diff).x, (diff).y)
  169.  
  170. /* Test whether a line is null. */
  171. #define line_is_null(p0, p1)\
  172.  (any_abs((p1).x - (p0).x) + any_abs((p1).y - (p0).y) < fixed_epsilon * 4)
  173.  
  174. /*
  175.  * Adjust the other control points of a curve proportionately when moving
  176.  * one end.  The Boolean argument indicates whether the point being
  177.  * adjusted is the one nearer the point that was moved.
  178.  */
  179. private fixed
  180. scale_delta(fixed diff, fixed dv, fixed lv, bool nearer)
  181. {    if ( dv == 0 )
  182.       return 0;
  183.     /*
  184.      * fixed_mult_quo requires non-negative 2nd and 3rd arguments,
  185.      * and also 2nd argument < 3rd argument.
  186.      * If it weren't for that, we would just use it directly.
  187.      *
  188.      * lv = 0 is implausible, but we have to allow for it.
  189.      */
  190.     if ( lv == 0 )
  191.       return (nearer ? diff : (fixed)0);
  192.     if ( lv < 0 )
  193.       lv = -lv, dv = -dv;
  194.     if ( dv < 0 )
  195.       dv = -dv, diff = -diff;
  196.     /* It's unlikely but possible that dv > lv.  Check for this here. */
  197.     if ( dv >= lv )
  198.       return diff * (int)(dv / lv) + fixed_mult_quo(diff, dv % lv, lv);
  199.     else
  200.       return fixed_mult_quo(diff, dv, lv);
  201. }
  202. private void
  203. adjust_curve_start(curve_segment *pcseg, const gs_fixed_point *pdiff)
  204. {    fixed dx = pdiff->x, dy = pdiff->y;
  205.     fixed end_x = pcseg->pt.x, end_y = pcseg->pt.y;
  206.     const segment *prev = pcseg->prev;
  207.     fixed lx = end_x - (prev->pt.x - dx), ly = end_y - (prev->pt.y - dy);
  208.  
  209.     add_hint_dxdy(pcseg->p1,
  210.               scale_delta(end_x - pcseg->p1.x, dx, lx, true),
  211.               scale_delta(end_y - pcseg->p1.y, dy, ly, true));
  212.     add_hint_dxdy(pcseg->p2,
  213.               scale_delta(end_x - pcseg->p2.x, dx, lx, false),
  214.               scale_delta(end_y - pcseg->p2.y, dy, ly, false));
  215. }
  216. private void
  217. adjust_curve_end(curve_segment *pcseg, const gs_fixed_point *pdiff)
  218. {    fixed dx = pdiff->x, dy = pdiff->y;
  219.     const segment *prev = pcseg->prev;
  220.     fixed start_x = prev->pt.x, start_y = prev->pt.y;
  221.     fixed lx = pcseg->pt.x - dx - start_x, ly = pcseg->pt.y - dy - start_y;
  222.  
  223.     add_hint_dxdy(pcseg->p1,
  224.               scale_delta(pcseg->p1.x - start_x, dx, lx, false),
  225.               scale_delta(pcseg->p1.y - start_y, dy, ly, false));
  226.     add_hint_dxdy(pcseg->p2,
  227.               scale_delta(pcseg->p2.x - start_x, dx, lx, true),
  228.               scale_delta(pcseg->p2.y - start_y, dy, ly, true));
  229. }
  230.  
  231. /*
  232.  * Propagate a final wraparound hint back through any null line segments
  233.  * to a possible curve.  pseg_last.pt has already been adjusted.
  234.  */
  235. private void
  236. apply_final_hint(segment *pseg_last, const gs_fixed_point *pdiff)
  237. {    segment *pseg;
  238.     for ( pseg = pseg_last; ; pseg = pseg->prev )
  239.       { segment *prev = pseg->prev;
  240.         switch ( pseg->type )
  241.           {
  242.           case s_curve:
  243.         adjust_curve_end(((curve_segment *)pseg), pdiff);
  244.         return;
  245.           case s_line:
  246.           case s_line_close:
  247.         if ( !line_is_null(prev->pt, pseg->pt) )
  248.           return;
  249.         add_hint_diff(prev->pt, *pdiff);
  250.         break;
  251.           default:        /* s_start */
  252.         return;
  253.           }
  254.       }
  255. }
  256.  
  257. /*
  258.  * Apply hints along a subpath.  If closing is true, consider the subpath
  259.  * closed; if not, we may add more to the subpath later.  In the latter case,
  260.  * don't do anything if the subpath is closed, because we already applied
  261.  * the hints.
  262.  */
  263. void
  264. type1_apply_path_hints(gs_type1_state *pcis, bool closing, gx_path *ppath)
  265. {    segment *pseg = pcis->hint_next;
  266. #define pseg_curve ((curve_segment *)pseg)
  267.     segment *pnext;
  268. #define pnext_curve ((curve_segment *)pnext)
  269.     subpath *psub = ppath->current_subpath;
  270.     /*
  271.      * hints holds the set of hints that have already been applied (if
  272.      * applicable) to pseg->pt, and hence should not be applied again.
  273.      */
  274.     int hints = pcis->hints_pending;
  275.     gs_fixed_point diff;
  276.  
  277.     if ( pseg == 0 )
  278.       {    /* Start at the beginning of the subpath. */
  279.         if ( psub == 0 )
  280.           return;
  281.         if ( psub->is_closed && !closing )
  282.           return;
  283.         pseg = (segment *)psub;
  284.         if ( pseg->next == 0 )
  285.           return;
  286.         hints = 0;
  287.         pcis->unmoved_start = psub->pt;
  288.         pcis->unmoved_end = psub->pt;
  289.       }
  290.     else
  291.       hints = pcis->hints_pending;
  292.     diff.x = diff.y = 0;
  293.     for ( ; (pnext = pseg->next) != 0; pseg = pnext )
  294.       {    int hints_next;
  295.         /* Apply hints to the end of the previous segment (pseg) */
  296.         /* and the beginning of this one (pnext). */
  297.         gs_fixed_point dseg;
  298.  
  299.         switch ( pnext->type )
  300.           {
  301.           case s_curve:
  302.             {    int hints_first =
  303.               line_hints(pcis, &pcis->unmoved_end,
  304.                      &pnext_curve->p1) & ~hints;
  305.             gs_fixed_point diff2;
  306.  
  307.             if ( pseg == (segment *)psub )
  308.               pcis->hints_initial = hints_first;
  309.             if ( hints_first )
  310.               apply_hints_at(pcis, hints_first, &pseg->pt, &dseg);
  311.             else
  312.               dseg.x = dseg.y = 0;
  313.             diff2.x = pseg->pt.x - pcis->unmoved_end.x;
  314.             diff2.y = pseg->pt.y - pcis->unmoved_end.y;
  315.             hints_next = line_hints(pcis, &pnext_curve->p2,
  316.                         &pnext->pt);
  317.             adjust_curve_start(pnext_curve, &diff2);
  318.             if ( hints_next )
  319.               { apply_hints_at(pcis, hints_next, &pnext_curve->p2,
  320.                        &diff);
  321.                 pcis->unmoved_end = pnext->pt;
  322.                 add_hint_diff(pnext->pt, diff);
  323.               }
  324.             else
  325.               pcis->unmoved_end = pnext->pt;
  326.             }    break;
  327.           case s_line_close:
  328.             /* Undo any initial hints propagated to the end. */
  329.             pnext->pt = pcis->unmoved_start;
  330.           default:        /* s_line, s_line_close */
  331.             if ( line_is_null(pnext->pt, pcis->unmoved_end) )
  332.               { /* This is a null line, just move it. */
  333.                 hints_next = hints;
  334.                 dseg.x = dseg.y = 0;  /* don't move p2 again */
  335.               }
  336.             else
  337.               { hints_next =
  338.                   line_hints(pcis, &pcis->unmoved_end, &pnext->pt);
  339.                 if ( hints_next & ~hints )
  340.                   apply_hints_at(pcis, hints_next & ~hints,
  341.                          &pseg->pt, &dseg);
  342.                 else
  343.                   dseg.x = dseg.y = 0;
  344.               }
  345.             if ( pseg == (segment *)psub )
  346.               pcis->hints_initial = hints_next;
  347.             pcis->unmoved_end = pnext->pt;
  348.             if ( hints_next )
  349.               apply_hints_at(pcis, hints_next, &pnext->pt, NULL);
  350.           }
  351.         if ( pseg->type == s_curve )
  352.           adjust_curve_end(pseg_curve, &dseg);
  353.         hints = hints_next;
  354.       }
  355.     if ( closing )
  356.       {    /* Handle the end of the subpath wrapping around to the start. */
  357.         /* This is ugly, messy code that we can surely improve. */
  358.         fixed ctemp;
  359.         /* Some fonts don't use closepath when they should.... */
  360.         bool closed =
  361.           (pseg->type == s_line_close ||
  362.            (ctemp = pseg->pt.x - psub->pt.x,
  363.             any_abs(ctemp) < float2fixed(0.1)) ||
  364.            (ctemp = pseg->pt.y - psub->pt.y,
  365.             any_abs(ctemp) < float2fixed(0.1)));
  366.         segment *pfirst = psub->next;
  367. #define pfirst_curve ((curve_segment *)pfirst)
  368.         int hints_first = pcis->hints_initial;
  369.         if ( closed )
  370.           {    /*
  371.              * Apply the union of the hints at both the end
  372.              * (pseg) and the start (psub) of the subpath.  Note
  373.              * that we have already applied hints at the end,
  374.              * and hints_first at the start.
  375.              */
  376.             int do_x, do_y;
  377.             gs_fixed_point diff2;
  378.  
  379.             if ( pcis->fh.axes_swapped )
  380.               do_x = hint_horz, do_y = hint_vert;
  381.             else
  382.               do_x = hint_vert, do_y = hint_horz;
  383.  
  384.             { /* Apply hints_first - hints to the end. */
  385.               int hints_end = hints_first & ~hints;
  386.               diff2.x =
  387.                 (hints_end & do_x ?
  388.                  psub->pt.x - pcis->unmoved_start.x : 0);
  389.               diff2.y =
  390.                 (hints_end & do_y ?
  391.                  psub->pt.y - pcis->unmoved_start.y : 0);
  392.             }
  393.  
  394.             { /* Apply hints - hints_first to the start. */
  395.               int hints_start = hints & ~hints_first;
  396.               diff.x =
  397.                 (hints_start & do_x ?
  398.                  pseg->pt.x - pcis->unmoved_end.x : 0);
  399.               diff.y =
  400.                 (hints_start & do_y ?
  401.                  pseg->pt.y - pcis->unmoved_end.y : 0);
  402.             }
  403.  
  404.             add_hint_diff(pseg->pt, diff2);
  405.             apply_final_hint(pseg, &diff2);
  406.             add_hint_diff(psub->pt, diff);
  407.           }
  408.         else
  409.           {    int hints_close =
  410.               line_hints(pcis, &pcis->unmoved_end,
  411.                      &pcis->unmoved_start);
  412.             hints_close &= ~(hints | hints_first);
  413.             if ( hints_close )
  414.               { apply_hints_at(pcis, hints_close, &pseg->pt, &diff);
  415.                 apply_final_hint(pseg, &diff);
  416.                 apply_hints_at(pcis, hints_close, &psub->pt, &diff);
  417.               }
  418.             else
  419.               diff.x = diff.y = 0;
  420.           }
  421.         if ( pfirst->type == s_curve )
  422.           adjust_curve_start(pfirst_curve, &diff);
  423.         pcis->hint_next = 0;
  424.         pcis->hints_pending = 0;
  425. #undef pfirst_curve
  426.       }
  427.     else
  428.       {    pcis->hint_next = pseg;
  429.         pcis->hints_pending = hints;
  430.       }
  431. #undef pseg_curve
  432. #undef pnext_curve
  433. }
  434.  
  435. /* ------ Individual hints ------ */
  436.  
  437. private const stem_hint *search_hints(P2(stem_hint_table *, fixed));
  438.  
  439. /*
  440.  * Adjust a point according to the relevant hints.
  441.  * dx or dy is > 0 for the upper edge, < 0 for the lower.
  442.  * The caller is responsible for checking use_hstem_hints or use_vstem_hints
  443.  * and not calling the find_xxx_hints routine if this is false.
  444.  * Note that if use_x/y_hints is false, no entries ever get made
  445.  * in the stem hint tables, so these routines will not get called.
  446.  */
  447.  
  448. private void
  449. apply_vstem_hints(gs_type1_state *pcis, int dy, gs_fixed_point *ppt)
  450. {    fixed *pv = (pcis->fh.axes_swapped ? &ppt->y : &ppt->x);
  451.     const stem_hint *ph = search_hints(&pcis->vstem_hints, *pv);
  452.  
  453.     if ( ph != 0 )
  454.     {    if_debug3('Y', "[Y]use vstem %d: %g (%s)",
  455.               (int)(ph - &pcis->vstem_hints.data[0]),
  456.               fixed2float(*pv),
  457.               (dy == 0 ? "?!" : dy > 0 ? "upper" : "lower"));
  458. #ifdef DEBUG
  459.         if ( dy == 0 )
  460.           { lprintf("dy == 0 in apply_vstem_hints!\n");
  461.             return;
  462.           }
  463. #endif
  464.         *pv += (dy > 0 ? ph->dv1 : ph->dv0);
  465.         if_debug1('Y', " -> %g\n", fixed2float(*pv));
  466.     }
  467. }
  468.  
  469. private void
  470. apply_hstem_hints(gs_type1_state *pcis, int dx, gs_fixed_point *ppt)
  471. {    fixed *pv = (pcis->fh.axes_swapped ? &ppt->x : &ppt->y);
  472.     const stem_hint *ph = search_hints(&pcis->hstem_hints, *pv);
  473.  
  474.     if ( ph != 0 )
  475.     {    if_debug3('Y', "[Y]use hstem %d: %g (%s)",
  476.               (int)(ph - &pcis->hstem_hints.data[0]),
  477.               fixed2float(*pv),
  478.               (dx == 0 ? "?!" : dx > 0 ? "upper" : "lower"));
  479. #ifdef DEBUG
  480.         if ( dx == 0 )
  481.           { lprintf("dx == 0 in apply_vstem_hints!\n");
  482.             return;
  483.           }
  484. #endif
  485.         *pv += (dx > 0 ? ph->dv1 : ph->dv0);
  486.         if_debug1('Y', " -> %g\n", fixed2float(*pv));
  487.     }
  488. }
  489.  
  490. /* Search one hint table for an adjustment. */
  491. private const stem_hint *
  492. search_hints(stem_hint_table *psht, fixed v)
  493. {    const stem_hint *table = &psht->data[0];
  494.     const stem_hint *ph = table + psht->current;
  495.  
  496.     if ( v >= ph->v0 && v <= ph->v1 )
  497.       return ph;
  498.     /* We don't bother with binary or even up/down search, */
  499.     /* because there won't be very many hints. */
  500.     for ( ph = &table[psht->count]; --ph >= table; )
  501.       if ( v >= ph->v0 && v <= ph->v1 )
  502.         {    psht->current = ph - table;
  503.         return ph;
  504.         }
  505.     return 0;
  506. }
  507.